package com.leetcode.test.tree;

import org.junit.Assert;
import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * https://leetcode-cn.com/explore/learn/card/data-structure-binary-tree/2/traverse-a-tree/9/
 * <p>
 * 解题：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/solution/er-cha-shu-de-ceng-ci-bian-li-by-leetcode/s
 */
public class 层次遍历 extends 二叉树Case {

	@Test
	public void test() {
//		 3
//		/ \
//	   9  20
//		 /  \
//		15   7

//		返回其层次遍历结果：
//		[
//        [3],
//        [9,20],
//        [15,7]
//		]
		TreeNode n3  = new TreeNode(3);
		TreeNode n9  = n3.left = new TreeNode(9);
		TreeNode n20 = n3.right = new TreeNode(20);
		TreeNode n15 = n20.left = new TreeNode(15);
		TreeNode n7  = n20.right = new TreeNode(7);

		List<List<Integer>> levels = levelOrder(n3);

		Assert.assertEquals(Arrays.asList(Arrays.asList(3), Arrays.asList(9, 20), Arrays.asList(15, 7)), levels);
	}

	public List<List<Integer>> levelOrder(TreeNode root) {
		List<List<Integer>> levels = new ArrayList<>();
		helper(root, 0, levels);
		return levels;
	}

	private void helper(TreeNode node, int level, List<List<Integer>> levels) {
		if (node == null) {
			return;
		}

		if (levels.size() <= level) {
			levels.add(new ArrayList<>());
		}

		levels.get(level).add(node.val);

		if (node.left != null) {
			helper(node.left, level + 1, levels);
		}
		if (node.right != null) {
			helper(node.right, level + 1, levels);
		}
	}
}
